A data network is a geographically distributed collection of nodes interconnected by communication links and segments for transporting data between end nodes, such as personal computers and workstations. Many types of data networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect nodes over dedicated private communication links located in the same general physical location, such as a building or campus. WANs, on the other hand, typically connect large numbers of geographically dispersed nodes over long-distance communication links, such as common carrier telephone lines. The Internet is an example of a WAN that connects networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
In a typical arrangement, end nodes in a data network are coupled via one or more intermediate nodes, such as routers. Routers are often configured to “route” data, such as packets, between various nodes in the network. Routing is typically performed at layer-3 (L3), which is the network layer of the Open Systems Interconnection Reference Model (OSI-RM). Routers often maintain forwarding databases (FDBs), which are typically configured to hold routing information including L3 addresses and interface information that the router uses to determine where data (e.g., data packets) are to be forwarded in order to reach their destination. For example, a router may have a routing database containing one or more entries wherein each entry contains a L3 destination address of a destination node and interface information about an interface on the router through which the destination node may be reached. A data packet containing a destination address that matches a destination address of an entry in the routing table is forwarded by the router to the interface specified by the matching entry for transfer to the destination node.
A router may execute one or more routing protocols that enable the router to route packets and exchange routing information with other routers in the network. The routers often use this information to configure (e.g., compute) their FDBs. The routing protocols may include distance-vector protocols, such as the Routing Information Protocol (RIP), or link-state protocols, such as the Intermediate-System-to-Intermediate-System (IS-IS) protocol and the Open Shortest Path First (OSPF) protocol. Routing information is typically exchanged between the routers in the form of advertisement messages. For example, nodes executing the IS-IS protocol exchange routing information using an advertisement message called a Link State Packet (LSP). Likewise, nodes executing the OSPF protocol exchange routing information using an advertisement message called a Link State Advertisement (LSA). An intermediate node that acquires an advertisement message may use information contained therein to update its FDB.
Data networks are increasingly being used to transport many forms of information including voice and video information. Voice information may be carried by various technologies including e.g., Voice over IP (VoIP). VoIP refers to a group of technologies that may be used to transmit voice information over data networks from a source (calling party) to a destination (called party). Such networks may include a plurality of voice agents that convert voice information from its traditional telephony form to a form that is suitable for packet transmission. In other words, the voice agent encodes, compresses and encapsulates the voice information into a plurality of data packets. Examples of voice agents include IP telephones, VoIP gateways, certain private branch exchanges (PBXs), personal computers (PCs) running communication applications, network devices providing voice gateway services and so on. A calling party uses a voice agent to initiate a VoIP call. Once the voice information has been converted into packet format, it is carried by the computer network to a second voice agent configured to serve the called party. The called party's agent processes (e.g., unencapsulates, decompresses and decodes) the data packets to produce the original voice information. This information may then be presented to the called party, accordingly.
Similarly, video information may be carried by various technologies that include video conferencing. Here, video information may be processed much like voice information is processed in VoIP systems, that is, the video information may be e.g., encoded and compressed, and encapsulated into data packets by a video agent at a calling party. The packets are then transferred via a data network using a protocol, such as e.g., the Real-Time Transport Protocol (RTP), to a video agent at the called party. The called party's agent processes (e.g., unencapsulates, decompresses and decodes) the data packets to produce the original video information which may be presented to the called party, accordingly.
Unlike static data files or records, voice and video information tends to be highly sensitive to delayed and lost packets as well as jitter. Delays in receiving packets or the loss of packets may seriously degrade the quality of the information as experienced at the called party's agent. Excessive jitter my trigger retransmission mechanisms which may further degrade the quality of information experienced at the called party's agent. Accordingly, packets carrying this information must ideally be delivered to the called party with a high probability of success and, in a timely and consistent manner.
Data networks typically incorporate various services and resources to obviate the effects of delayed and lost packets and jitter, and to ensure successful, timely and consistent delivery of data packets. In particular, an intermediate node (e.g., a router) in the data network may provide specific resources and/or services that are configured to affect the rate at which traffic moves through the node in an effort to avoid traffic congestion in the network that may lead to lost or delayed traffic, and jitter. These resources and/or services may include priority queues, filter settings, traffic shapers, queue selection strategies, congestion control algorithms and the like. Depending on the selection or allocation of such resources and services within the network, different types of traffic may be forwarded at different rates and at different priorities in the network in an effort to avoid congestion and ensure timely and consistent delivery of the traffic.
Some applications may incorporate unidirectional data flows configured to transfer time-sensitive traffic from a source (sender) in a data network to a destination (receiver) in the network in accordance with a certain “quality of service” (QoS) associated with each data flow. Here, network resources may be reserved for a unidirectional flow to ensure that the QoS associated with the data flow is maintained. The Resource Reservation Protocol (RSVP) is a network-control protocol that enables applications to reserve resources for data flows in order to obtain a certain degree of QoS for the data flows. RSVP works in conjunction with routing protocols to reserve resources for data flows in a data network in order to establish a level of QoS required by the data flows. RSVP is defined in R. Braden, et al., “Resource ReSerVation Protocol (RSVP),” Request For Comments (RFC) 2205.
Pursuant to RSVP, a data flow is a sequence of messages that have the same source address and same destination address (unicast or multicast). Data flows are unidirectional in that data travels on a data flow from a sender to a receiver. A session is a collection of one or more data flows that have the same unicast or multicast destination address. Sessions typically utilize port and protocol numbers much like data flows. Sessions differ from data flows in that a session may have multiple senders, whereas a data flow only originates from a single sender.
In a protocol, such as RSVP, signaling messages are used to reserve resources for data flows. RSVP defines two fundamental types of signaling messages, a RSVP path (Path) message and a RSVP reservation request (Resv) message. Path messages are typically sent by senders to identify them and indicate the resources (e.g., bandwidth) needed to receive their programming or content. These messages proceed hop-by-hop on a path through the data network to one or more receivers. The Path messages make intermediate nodes on the path aware of the possibility that a reservation of resources may be required. If a receiver is interested in the programming or content offered by a particular sender, it responds with a RSVP Resv message to reserve resources for a data flow between the sender and receiver. The Resv message specifies resources needed to accommodate the data flow. The Resv message travels hop-by-hop on the same path taken by the Path message but in the reverse direction back to the sender. At each hop, the corresponding intermediate node establishes a reservation for the receiver by setting aside (reserving) resources specified in the Resv message for the data flow. These resources are immediately made available to the data flow. If resources are not available, the reservation may be refused explicitly so that the receiver knows it cannot depend on the corresponding resources being devoted to its traffic. By using RSVP, packets carrying, e.g., time-sensitive information can be accorded the resources and services they need to ensure timely and consistent delivery.
The RSVP protocol supports individual reservations and aggregate reservations. An individual reservation relates to a single reservation associated with a single data flow between a sender and a receiver. An aggregate reservation relates to a reservation that is an aggregate of a plurality of reservations who all share an “aggregate region.” An aggregation region refers to a region in a data network where some number of data flows flow through the same set of intermediate nodes. In other words, the data flows travel through the same intermediate nodes in the data network in the aggregation region. Like individual reservations, aggregate reservations have a sender (“aggregator”) and a receiver (“deaggregator”) associated with the aggregate reservation. Flows associated with reservations belonging to an aggregate reservation are aggregated (bundled) at the aggregate reservation's “aggregator” and “deaggregated” (unbundled) at the aggregate reservation's “deaggregator.”
Reservation protocols, such as RSVP, often support the prioritization and preemption of reservations. Prioritization generally relates to a preference (priority) given to a reservation with respect to allocating resources to the reservation over other reservations. Preemption generally relates to preempting an existing lower priority reservation in order to reallocate its resources to a newer higher-priority reservation. Typically, the preempted reservation is preempted by: (1) tearing down (removing) the entire reservation by sending an error message to the reservation's receiver and (2) reallocating its resources as necessary to the newer reservation. Any remaining resources from the preempted reservation that were not allocated to the newer reservation are made available for future reservations.
One problem with the preempting technique described above is that it is inefficient from a resource allocation standpoint. For example, assume an existing reservation is an aggregate reservation containing hundreds of individual reservations wherein each individual reservation is for a data flow that carries a telephone call. Further, assume a newer higher-priority individual reservation for a data flow that carries a single telephone call is being processed and that the higher-priority reservation only needs a small amount of resources allocated to the existing reservations associated with the aggregate reservation. According to existing techniques, the entire aggregate reservation must be preempted (e.g., torn down) in order to accommodate the newer reservation. This may mean inconveniencing all of the existing telephone calls associated with the existing individual reservations in order to accommodate a single higher-priority call even though the higher-priority call may be accommodated by only inconveniencing a single existing telephone call. Typically, the calls would not be dropped outright; however, the calls would lose their guaranteed resources thus potentially degrading their quality.
Another problem with the above-described preemption technique is that it may be difficult for the preempted reservation to reestablish itself after it has been preempted. For example, existing reservation protocols do not provide an indication as to how much resources are available to the preempted reservation. Thus, the preempted reservation must guess as to how much resources are available in order to reestablish the reservation. If the guess is incorrect, the attempt will fail. Furthermore, an intervening reservation may further reduce the amount of available resources, further complicating efforts to reestablish the preempted reservation.